package Leetcode;
import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class buildTree {
    // 使用HashMap存储中序遍历数组中值到索引的映射，以便快速查找根节点的索引
    Map<Integer, Integer> map = new HashMap<>();

    /**
     * 根据给定的前序和中序遍历数组构建二叉树
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @return 构建的二叉树根节点
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 遍历中序遍历数组，将值和索引的映射存入HashMap
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 调用递归函数构建二叉树
        return buildTree(preorder, inorder, 0, preorder.length, 0, inorder.length);
    }

    /**
     * 递归构建二叉树
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @param preStart 前序遍历数组的起始索引
     * @param preEnd 前序遍历数组的结束索引
     * @param inStart 中序遍历数组的起始索引
     * @param inEnd 中序遍历数组的结束索引
     * @return 当前递归构建的子树根节点
     */
    public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){
        // 递归终止条件：中序或前序数组索引越界
        if (inStart >= inEnd || preStart >= preEnd){
            return null;
        }
        // 获取当前子树根节点的值
        int rootValue = map.get(preorder[preStart]);
        // 创建当前子树的根节点
        TreeNode root = new TreeNode(inorder[rootValue]);
        // 如果前序遍历数组只有一个元素，说明到达叶子节点，返回当前节点
        if (preorder.length == 1) return root;
        // 计算左子树的长度
        int lenOfLeft = rootValue - inStart;
        // 递归构建左子树
        root.left = buildTree(preorder, inorder, preStart + 1, preStart + lenOfLeft + 1, inStart, rootValue);
        // 递归构建右子树
        root.right = buildTree(preorder, inorder, preStart + lenOfLeft + 1, preEnd, rootValue + 1, inEnd);
        // 返回当前子树的根节点
        return root;
    }
}
